pub fn goldbach_conjecture() -> u64 {
    const N: u64 = 100000;
    let primes = eratosthenes_sieve(N as usize);
    let mut res: Vec<u64> = Vec::new();
    for i in 4..N {
        // if i is prime, skip
        if is_prime(i, &primes) {
            continue;
        }
        // if i is even, skip
        if i % 2 == 0 {
            continue;
        }
        let matched = judge_goldbach(i, &primes);
        if !matched {
            res.push(i);
        }
        if res.len() == 2 {
            break;
        }
    }
    res.iter().sum()
}

// judge whether an odd composite number can be written as the sum of a prime and twice a square
fn judge_goldbach(n: u64, primes: &Vec<bool>) -> bool {
    for i in 2..n {
        if is_prime(i, primes) && is_square((n - i) / 2) {
            return true;
        }
    }
    false
}

// judge whether a number is prime
fn is_prime(n: u64, primes: &Vec<bool>) -> bool {
    primes[n as usize]
}

// judge whether a number is a square number
fn is_square(n: u64) -> bool {
    let x = (n as f64).sqrt() as u64;
    x * x == n
}

// use the sieve of Eratosthenes to generate prime numbers
fn eratosthenes_sieve(n: usize) -> Vec<bool> {
    let mut primes = vec![true; n];
    primes[0] = false;
    primes[1] = false;
    let mut p = 2;
    while p * p <= n {
        if primes[p] {
            let mut i = p * p;
            while i < n {
                primes[i] = false;
                i += p;
            }
        }
        p += 1;
    }
    primes
}
